#include <vector>
#include <iostream>
#include <iterator>
#include <cstdlib>
#include "gtest/gtest.h"

//二分查找，循环实现，O(lgn)
template <class Comparable>
long binSearch(const std::vector<Comparable> &A, const Comparable &x) {
    long low = 0, high = A.size()-1;
    //while (low < high) {//循环终止条件可能无法达到，
    while (low <= high) {
        //long mid = (low+high)/2; //当整数很大时，这种求和可能会溢出
        long mid = low + (high - low)/2;
        if (x == A[mid]) {
            return mid;
        } else if (x < A[mid]) {
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return -1;
}

//二分查找，递归实现，O(lgn)
template <class Comparable>
long binSearch2(const std::vector<Comparable> &A, const Comparable &x, long low, long high) {
    if (low > high) {
        return -1;
    }

    long mid = (low+high)/2;
    if (x < A[mid]) {
        return binSearch2(A, x, low, mid-1);
    } else if (x > A[mid]) {
        return binSearch2(A, x, mid+1, high);
    } else {
        return mid;
    }
}

template <class Comparable>
long binSearch2(const std::vector<Comparable> &A, const Comparable &x) {
    return binSearch2(A, x, 0, A.size()-1);
}

//找出一个有序数组A中值等于x的
//元素的序号，如果有多个元素满
//足这个条件，则返回其中序号最大的
//二分查找，编程之美上面的错误实现
//无法通过测试
template <class Comparable>
int binSearchError(const std::vector<Comparable> &A, const Comparable &x) {
    int minIndex = 0, maxIndex = A.size()-1;
    while (minIndex < maxIndex) {
        int midIndex = (minIndex + maxIndex)/2;
        if (A[midIndex] <= x) {
            minIndex = midIndex;
        } else {
            maxIndex = midIndex-1;
        }
    }
    if (A[maxIndex] == x) {
        return maxIndex;
    } else {
        return -1;
    }
}

//找出一个有序数组A中值等于x的
//元素的序号，如果有多个元素满
//足这个条件，则返回其中序号最大的
//二分查找，编程之美上面的正确实现
template <class Comparable>
int binSearch3(const std::vector<Comparable> &A, const Comparable &x) {
    int minIndex = 0, maxIndex = A.size()-1;

    //循环结束有两种情况
    //若maxIndex为偶数，则minIndex == maxIndex
    //否则就是minIndex == maxIndex-1
    while (minIndex < maxIndex-1) {
        int midIndex = minIndex + (maxIndex - minIndex)/2;
        if (A[midIndex] <= x) {
            minIndex = midIndex;
        } else {
            //不需要midIndex-1，防止minIndex == maxIndex
            maxIndex = midIndex;
        }
    }

    //先判断最大序号的值
    if (A[maxIndex] == x) {
        return maxIndex;
    } else if (A[minIndex] == x) {
        return minIndex;
    } else {
        return -1;
    }
}

//test distinct elements
TEST(binSearch, distinct) {
    for (int n = 0; n < 1000; ++n) {
        std::vector<int> vt(n+1);
        for (int i = 0; i <= n; ++i) {
            vt[i] = 10*i;
        }

        for (int i = 0; i < n; ++i) {
            EXPECT_TRUE(binSearch(vt, 10*i) == i);
            EXPECT_TRUE(binSearch(vt, 10*i - 5) == -1);
        }
        EXPECT_TRUE(binSearch(vt, 10*n - 5) == -1);
        EXPECT_TRUE(binSearch(vt, 10*n) != -1);
    }
}

//test equal elements
TEST(binSearch, equal) {
    for (int n = 0; n < 10000; ++n) {
        std::vector<int> vt(n);
        for (int i = 0; i < n; ++i) {
            vt[i] = 10;
        }
        if (n == 0) {
            EXPECT_TRUE(binSearch(vt, 10) == -1);
        } else {
            EXPECT_TRUE(0 <= binSearch(vt, 10) && binSearch(vt, 10) < n);
        }
        EXPECT_TRUE(binSearch(vt, 5) == -1);
        EXPECT_TRUE(binSearch(vt, 15) == -1);
    }
}

//test distinct elements
TEST(binSearch2, distinct) {
    for (int n = 0; n < 1000; ++n) {
        std::vector<int> vt(n+1);
        for (int i = 0; i <= n; ++i) {
            vt[i] = 10*i;
        }

        for (int i = 0; i < n; ++i) {
            EXPECT_TRUE(binSearch2(vt, 10*i) == i);
            EXPECT_TRUE(binSearch2(vt, 10*i - 5) == -1);
        }
        EXPECT_TRUE(binSearch2(vt, 10*n - 5) == -1);
        EXPECT_TRUE(binSearch2(vt, 10*n) != -1);
    }
}

//test equal elements
TEST(binSearch2, equal) {
    for (int n = 0; n < 10000; ++n) {
        std::vector<int> vt(n);
        for (int i = 0; i < n; ++i) {
            vt[i] = 10;
        }
        if (n == 0) {
            EXPECT_TRUE(binSearch2(vt, 10) == -1);
        } else {
            EXPECT_TRUE(0 <= binSearch2(vt, 10) && binSearch2(vt, 10) < n);
        }
        EXPECT_TRUE(binSearch2(vt, 5) == -1);
        EXPECT_TRUE(binSearch2(vt, 15) == -1);
    }
}

//test distinct elements
TEST(binSearch3, distinct) {
    for (int n = 0; n < 1000; ++n) {
        std::vector<int> vt(n+1);
        for (int i = 0; i <= n; ++i) {
            vt[i] = 10*i;
        }

        for (int i = 0; i < n; ++i) {
            EXPECT_TRUE(binSearch3(vt, 10*i) == i);
            EXPECT_TRUE(binSearch3(vt, 10*i - 5) == -1);
        }
        EXPECT_TRUE(binSearch3(vt, 10*n - 5) == -1);
        EXPECT_TRUE(binSearch3(vt, 10*n) != -1);
    }
}

//test equal elements
TEST(binSearch3, equal) {
    for (int n = 0; n < 10000; ++n) {
        std::vector<int> vt(n);
        for (int i = 0; i < n; ++i) {
            vt[i] = 10;
        }
        if (n == 0) {
            EXPECT_TRUE(binSearch3(vt, 10) == -1);
        } else {
            EXPECT_TRUE(0 <= binSearch3(vt, 10) && binSearch3(vt, 10) < n);
            EXPECT_TRUE(binSearch3(vt, 10) == n-1);
        }
        EXPECT_TRUE(binSearch3(vt, 5) == -1);
        EXPECT_TRUE(binSearch3(vt, 15) == -1);
    }
}

int main(int argc, char *argv[])
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
